class TrieNode:
    def __init__(self):
        # 当前节点的子结点
        self.children = {}
        # 当前节点是否为结尾
        self.is_end_of_word = False
        # 当前节点查询失败后转到下一个节点
        self.failure_link = None
        # 当前节点的字符
        self.char = ""
        # 当前节点的字符叠加,用于记录叶子节点的对应字符串
        self.sumChart = ""
        # 叶子节点的单词
        self.word = ""

def build_trie(patterns):
    root = TrieNode()
    for pattern in patterns:
        currentNode = root
        for char in pattern:
            # 如果这个字符并没有出现在当前节点的子结点中，那么就要创造一个这样的节点作为子结点
            if char not in currentNode.children:
                childNode = TrieNode()
                # 赋值字符
                childNode.char = char
                # 子结点的累加字符为当前节点的累加字符并添加当前的字符
                childNode.sumChart = currentNode.sumChart + char
            # 当前子结点已经存在，直接赋值即可
            else:
                childNode = currentNode.children[char]
            currentNode.children[char] = childNode
            # 然后继续遍历子结点
            currentNode = currentNode.children[char]
        currentNode.word = currentNode.sumChart
        currentNode.is_end_of_word = True
    return root

def add_failure_links(root):
    queue = []
    # 每个根节点下的节点一旦失败，就会返回到根节点重新查询
    for child in root.children.values():
        queue.append(child)
        child.failure_link = root

    # 层序遍历
    while queue:
        current_node = queue.pop(0)
        # 遍历当前节点
        for char, childNode in current_node.children.items():
            # 将当前节点的子结点存入队列
            queue.append(childNode)
            # 拿出失败时的节点
            failure_node = current_node.failure_link
            '''
            对于状态匹配失败的节点a，
            如果其父节点的失败节点可以根据该节点a的跳转字符成功转移状态到另一节点b，那么就将失败节点a指向该节点b；
            如果其父节点的失败节点不能根据该节点的跳转字符转移状态到另一节点，那么就将失败节点a将检查其父节点的父节点的失败节点是否满足上述条件；
            依次递推，如果回溯到根节点还未找到，那就指向将失败节点指向根节点。
            '''
            while failure_node and char not in failure_node.children:
                failure_node = failure_node.failure_link
            
            # 如果当前的failure_node存在并且其以char为值的子结点也存在
            # 当前的childNode节点的失败指针就指向failure_node节点的失败指针指向的存有该char值的子结点
            if failure_node and failure_node.children[char]:
                childNode.failure_link = failure_node.children[char]
                # 这里需要注意，如果当前的childNode节点的失败时指向的节点是叶节点，其实也意味着
                # 查找到这个子结点的时候，已经匹配到了一个字串了
                if childNode.failure_link.is_end_of_word:
                    # 当childNode为非根节点的时候需要赋值word为其失败后指向节点的word
                    if not childNode.is_end_of_word:
                        childNode.is_end_of_word = True
                        # 既然当前的节点表示已经匹配到了一个字串，那么相应的该节点应该也是有一个单词的
                        childNode.word = childNode.failure_link.word
            else:
                childNode.failure_link = root

def search(text, patterns):
    root = build_trie(patterns)
    add_failure_links(root)

    current_node = root
    matches = []

    for i, char in enumerate(text):
        # 如果当前的节点存在，且当前字符匹配失败，就去找失败节点
        while current_node and char not in current_node.children:
            current_node = current_node.failure_link

        # 如果当前的节点为空，其实就意味着找到了根节点的失败节点了，
        # 此时表明查询失败重新从根节点开始查询
        if not current_node:
            current_node = root
            continue
        
        # 如果char存在于当前的节点的子结点中，说明成功匹配
        # 递进去下一个节点
        current_node = current_node.children[char]
        # 如果此时匹配到的值已经是匹配关键词的末尾了，说明匹配中了一个字串
        # 记录下来
        if current_node.is_end_of_word:
            matches.append((current_node.word, (i - len(current_node.word) + 1, i)))
            if current_node.failure_link.is_end_of_word:
                tempNode = current_node.failure_link
                matches.append((tempNode.word, (i - len(tempNode.word) + 1, i)))
    # 数据处理
    data = list(set(matches))
    result = []
    for item in data:
        tempObj = {
            "patternString": item[0],
            "matchStartIndex": item[1][0],
            "matchEndIndex": item[1][1]
        }
        result.append(tempObj)
    # 按matchEndIndex排序
    sortedResult = sorted(result, key=lambda x: (x['matchEndIndex'], x['matchStartIndex']))
    return sortedResult

# Example
text = "abccab"
patterns = ["ab", "bc", "ca", "ccab"]
result = search(text, patterns)
for item in result:
    print(item)
